package com.lw.leetcode.back.b;

/**
 * Created with IntelliJ IDEA.
 * 1391. 检查网格中是否存在有效路径
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/21 22:23
 */
public class HasValidPath {

    public static void main(String[] args) {
        HasValidPath test = new HasValidPath();

        // ture
//        int[][] arr = {{1, 1, 3}};

        // ture
//        int[][] arr = {{2, 4, 3}, {6, 5, 2}};

        // ture
        int[][] arr = {{4, 1}, {6, 1}};

        boolean b = test.hasValidPath(arr);
        System.out.println(b);
    }

    private int m;
    private int n;
    private int[][] grid;

    public boolean hasValidPath(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        if (m == 1 && n == 1) {
            return true;
        }
        this.grid = grid;
        int v = grid[0][0];
        if (v == 1 || v == 6) {
            return find(0, 1, 4);
        }
        if (v == 2 || v == 3) {
            return find(1, 0, 2);
        }
        if (v == 4) {
            return find(1, 0, 2) || find(0, 1, 4);
        }
        return false;
    }

    private boolean find(int x, int y, int flag) {
        if (x < 0 || y < 0 || x == m || y == n || grid[x][y] == 0) {
            return false;
        }
        int v = grid[x][y];
        if (x == m - 1 && y == n - 1) {
            if (flag == 2) {
                return v == 2 || v == 5 || v == 6;
            }
            if (flag == 4) {
                return v == 1 || v == 3 || v == 5;
            }
            return false;
        }
        grid[x][y] = 0;
        if (v == 1) {
            if (flag == 4) {
                return find(x, y + 1, 4);
            }
            if (flag == 3) {
                return find(x, y - 1, 3);
            }
            return false;
        }
        if (v == 2) {
            if (flag == 1) {
                return find(x - 1, y, 1);
            }
            if (flag == 2) {
                return find(x + 1, y, 2);
            }
            return false;
        }
        if (v == 3) {
            if (flag == 4) {
                return find(x + 1, y, 2);
            }
            if (flag == 1) {
                return find(x, y - 1, 3);
            }
            return false;
        }
        if (v == 4) {
            if (flag == 3) {
                return find(x + 1, y, 2);
            }
            if (flag == 1) {
                return find(x, y + 1, 4);
            }
            return false;
        }
        if (v == 5) {
            if (flag == 2) {
                return find(x, y - 1, 3);
            }
            if (flag == 4) {
                return find(x - 1, y, 1);
            }
            return false;
        }
        if (flag == 2) {
            return find(x, y + 1, 4);
        }
        if (flag == 3) {
            return find(x - 1, y, 1);
        }
        return false;
    }

}
